package 回溯;

import java.util.ArrayList;
import java.util.List;


/**
 * https://leetcode.cn/problems/combination-sum/
 *
 * 题解：https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247493581&idx=1&sn=5297ba176d635b3f278e88c3ff90de9b&chksm=9bd419c5aca390d3d72ea860edea38858ae5d4c8a62dc06accfa8c9030128c4dfeac1a98dc16&scene=178&cur_album_id=2165135739779448832#rd
 *
 *
 * 输入：candidates = [2,3,6,7], target = 7
 * 输出：[[2,2,3],[7]]
 * 解释：
 * 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 * 7 也是一个候选， 7 = 7 。
 * 仅有这两种组合。
 * 示例 2：
 *
 * 输入: candidates = [2,3,5], target = 8
 * 输出: [[2,2,2,2],[2,3,3],[3,5]]
 * */
public class _39_组合总和 {

    List<List<Integer>> resultList;
    List<Integer> res;

    int[] candidates;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.res = new ArrayList<>();
        this.resultList = new ArrayList<>();
        this.candidates = candidates;
        dfs(0, target);
        return resultList;
    }

    private void dfs(int posi,int target) {
        if (target == 0) {
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < res.size(); i++) {
                result.add(res.get(i));
            }
            resultList.add(result);
            return;
        }

        if(target < 0) return;

        for (int i = posi; i < candidates.length; i++) {
            res.add(candidates[i]);
            dfs(i,target-candidates[i]);
            res.remove(res.size()-1);
        }
    }

}
